Thực đơn
Thuật_toán_Ford–Fulkerson Độ phức tạpBằng cách thêm luồng trên đường tăng vào luồng đã được thiết lập trên đồ thị, ta sẽ đạt đến luồng cực đại khi trên đồ thị không còn tìm được thêm đường tăng luồng nào nữa. Tuy nhiên, không chắc chắn là tình huống này sẽ đạt được, do vậy điều tốt nhất có thể được đảm bảo là: nếu thuật toán kết thúc thì kết quả sẽ là lời giải đúng. Trong trường hợp thuật toán chạy vô hạn, luồng có thể không hội tụ về phía luồng cực đại. Tuy nhiên, tình huống này chỉ xảy ra với luồng có giá trị vô tỷ. Khi khả năng thông qua là các số tự nhiên, thời gian chạy của thuật toán Ford-Fulkerson bị chặn bởi O(E*f), trong đó E là số cung của đồ thị và f là luồng cực đại trên đồ thị. Điều này là bởi vì mỗi đường tăng được tìm ra trong thời gian O(E) và nó làm tăng luồng với một lượng có giá trị nguyên không nhỏ hơn 1.
Một biến thể của thuật toán Ford-Fulkerson bảo đảm sự kết thúc và thời gian chạy không phụ thuộc vào giá trị luồng cực đại là thuật toán Edmonds-Karp, chạy trong thời gian O(VE2).
Thực đơn
Thuật_toán_Ford–Fulkerson Độ phức tạpLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ thiên văn học Thuật ngữ lý thuyết đồ thị Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật toán Kruskal Thuật ngữ ngữ âm họcTài liệu tham khảo
WikiPedia: Thuật_toán_Ford–Fulkerson http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/ma... http://laptrinh.sourceforge.net/hoctap/maxflow/ https://web.archive.org/web/20060717041622/http://...